package leetcode_day._2021._202108._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/8/18 16:22
 * 学生出勤记录 II
 * 算法：动态规划
 * dp[n][i][k] 表示填入 n 个字符、i 个 A、k 个 L 时满足条件的数量
 * i 要小于 2，k 表示 n 个字符中最后连续 K 个 L
 * 从 dp[n][i][k] 出发，所能得到的值
 */
public class _18_552 {

    public int checkRecord(int n) {
        int mod = (int) 1e9 + 7;
        int[][][] dp = new int[n + 1][2][3];
        dp[0][0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    // A, 这里的 k 要为 0
                    if (j != 1) dp[i + 1][j + 1][0] = (dp[i + 1][j + 1][0] + dp[i][j][k]) % mod;
                    // L
                    if (k != 2) dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod;
                    // P, 这里的 k 要为 0
                    dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k]) % mod;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) ans = (ans + dp[n][i][j]) % mod;
        }
        return ans;
    }

}
